{\magonebf  6.2 Two-dimensional dictionaries (d2\_dictionary)}

An instance $D$ of the data type $d2\_dictionary$ is a collection of items 
($dic2\_item$). Every item in $D$ contains a key from a linearly ordered 
data type $K1$, a key from a linearly ordered data type $K2$, and an 
information from a data type $I$. $K1$ and $K2$ are called the key types 
of $D$, and $I$ is called the information type of $D$. The number
of items in $D$ is called the size of $D$. A two-dimensional dictionary of size
zero is said to be  empty. We use $<k_1,k_2,i>$ to denote the item with first 
key $k_1$, second key $k_2$, and information $i$. For each pair 
$(k_1,k_2) \in K1 \times K2$ there is at most one item $<k_1,k_2,i> \in D$.
Additionally to the normal dictionary operations, the data type $d2\_dictionary$
supports rectangular range queries on $K1\times K2$.


\bigskip
{\bf 1. Declaration of a two-dimensional dictionary type}

\declthree d2\_dictionary K1 K2 I

introduces a new data type with name \name\ consisting of all 
two-dimensional dictionaries with key types $K1$ and $K2$ and 
information type $I$. \precond $K1$ and $K2$ are linearly ordered.


\bigskip
{\bf 2. Creation of a two-dimensional dictionary}


\create D {}

creates an instance \var\ of type \name\ and initializes \var\ to the 
empty dictionary. 



\bigskip
{\bf 3. \operations}

\+\cleartabs & \hskip 3truecm & \hskip 5truecm &\cr
\+\op K1               key1 {dic2\_item\ it}  
                            {returns the first key of item $it$.}
\+\nop                      {\precond $it$ is an item in \var.}
\smallskip
\+\op K2               key2 {dic2\_item\ it}  
                            {returns the second key of item $it$.}
\+\nop                      {\precond $it$ is an item in \var.}
\smallskip
\+\op I                inf {dic2\_item\ it}   
                            {returns the information of item $it$.}
\+\nop                      {\precond $it$ is an item in \var.}
\smallskip
\+\op dic2\_item       max\_key1 {}   
                            {returns the item with maximal first key.}
\smallskip
\+\op dic2\_item       max\_key2 {}   
                            {returns the item with maximal second key.}
\smallskip
\+\op dic2\_item       min\_key1 {}   
                            {returns the item with minimal first key.}
\smallskip
\+\op dic2\_item       min\_key2 {}   
                            {returns the item with minimal second key.}

\vfill\eject

\+\op dic2\_item       insert {K1\ k_1,\ K2\ k_2,\ I\ i}  {}
\+\nop                      {associates the information $i$ with the keys}
\+\nop                      {$k_1$ and $k_2$. If there is an item $<k_1,k_2,j>$}
\+\nop                      {in \var\ then $j$ is replaced by i, else a new }
\+\nop                      {item $<k_1,k_2,i>$ is added to $D$. In both }
\+\nop                      {cases the item is returned.}
\smallskip
\+\op dic2\_item       lookup {K1\ k_1,\ K2\ k_2}  {}
\+\nop                      {returns the item with keys $k_1$ and $k_2$}
\+\nop                      {(nil if no such item exists in \var).}
\smallskip
\+\op list(dic2\_item) range\_search {K1\ a,\ K1\ b,\ K2\ c,\ K2\ d} {}
\+\nop                      {returns the list of all items $<k_1,k_2,i> \in$ \var} 
\+\nop                      {with $a \le k_1 \le b$ and $c \le k_2 \le d$.}
\smallskip
\+\op list(dic2\_item) all\_items {}
                            {returns the list of all items of \var.}
\smallskip
\+\op void             del {K1\ k_1,\ K2\ k_2}         
                            {deletes the item with keys $k_1$ and $k_2$}
\+\nop                      {from \var.}
\smallskip
\+\op void             del\_item {dic2\_item\ it}   
                            {removes item $it$ from \var.}
\+\nop                      {\precond $it$ is an item in \var.}
\smallskip
\+\op void             change\_inf {dic2\_item\ it,\ I\ i} {}
\+\nop                      {makes $i$ the information of item $it$.}
\+\nop                      {\precond $it$ is an item in \var.}
\smallskip
\+\op void             clear {}           
                            {makes \var\ the empty d2\_dictionary.}
\smallskip 
\+\op bool             empty {}           
                            {returns true if \var\ is empty, false otherwise.}
\smallskip 
\+\op int  size {}          
                            {returns the size of \var.}



\bigskip
{\bf 4. Iteration}

{\bf forall\_dic2\_items}($i,D$) 
$\{$ ``the items of $D$ are successively assigned to $i$ '' $\}$



\bigskip
{\bf 5. Implementation}

Two-dimensional dictionaries are implemented by dynamic two-dimensional range
trees based on BB[$\alpha$] trees. Operations insert, lookup, del\_item, del 
take time $O(\log^2 n)$,  range\_search takes time $O(k + \log^2 n)$, where
$k$ is the size of the returned list, key, inf, empty, size, change\_inf
take time $O(1)$, and clear takes time $O(n\log n)$. Here $n$ is the current 
size of the dictionary. The space requirement is $O(n\log n)$.

